"""
编写一个程序，找到两个单链表相交的起始节点。
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3


例如，下面的两个链表：

"""


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        def maxDeep(head):
            if not head: return 0
            if not head.next: return 1
            return maxDeep(head.next)+1
        la = maxDeep(headA)
        lb = maxDeep(headB)
        if la > lb:
            l = la-lb
            while l > 0:
                headA = headA.next
                l -= 1
        elif la < lb:
            l = lb-la
            while l > 0:
                headB = headB.next
                l -= 1
        while headA and headB :
            if headA.val == headB.val:
                return headA
            headA = headA.next
            headB = headB.next
        return

a1 = ListNode(1)
a2 = ListNode(2)
a3 = ListNode(3)
a4 = ListNode(4)
a5 = ListNode(5)
a4.next = a5
a3.next = a4
a1.next = a3
a2.next = a3
s= Solution()
print(s.getIntersectionNode(a1,a2))